// 分治函数：将小于基准值的放左侧，大于的放右侧，并返回基准值索引
function partition(array, left, right) {
    let pivot = array[right]; // 选择最后一个元素作为基准值
    let pivotIndex = right;
    right--; // 开始前将 right 移到 pivot 左侧
    while (left <= right) {
        // left 向右移动，直到找到不小于 pivot 的元素
        while (left <= right && array[left] < pivot) {
            left++;
        }
        // right 向左移动，直到找到不大于 pivot 的元素
        while (left <= right && array[right] > pivot) {
            right--;
        }
        // 如果 left 小于等于 right，则交换
        if (left <= right) {
            [array[left], array[right]] = [array[right], array[left]];
            left++;
            right--;
        }
    }
    // 将 pivot 交换到正确位置
    [array[left], array[pivotIndex]] = [array[pivotIndex], array[left]];
    return left; // 返回 pivot 最终位置
}

function quickSort(array) {
    function QuickSort(array, left, right) {
        if (left < right) {
            let index = partition(array, left, right); // 返回 pivot 的新位置
            QuickSort(array, left, index - 1);         // 递归左侧
            QuickSort(array, index + 1, right);        // 递归右侧
        }
    }
    QuickSort(array, 0, array.length - 1);
}


// 测试函数
function testInsertionSort() {
    let arr = [];
    for (let i = 0; i < 10; i++) {
        arr.push(Math.floor(Math.random() * 100));
    }
    
    console.log("排序前:", arr);
    quickSort(arr);
    console.log("排序后:", arr);
    
    // 验证排序结果
    for (let i = 0; i < arr.length - 1; i++) {
        if (arr[i] > arr[i + 1]) {
            console.log("排序失败!");
            return;
        }
    }
    console.log("排序成功!");
}

// 运行测试
testInsertionSort();